package com.atguigu.tree;

import java.text.SimpleDateFormat;
import java.util.Date;

public class HeapSort {

  public static void main(String[] args) {
    // 要求将数组进行升序排序
    // int arr[] = {4, 6, 8, 5, 9};
    // 创建要给80000个的随机的数组
    int[] arr = new int[8000000];
    for (int i = 0; i < 8000000; i++) {
      arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
    }

    System.out.println("排序前");
    Date data1 = new Date();
    SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String date1Str = simpleDateFormat.format(data1);
    System.out.println("排序前的时间是=" + date1Str);

    heapSort(arr);

    Date data2 = new Date();
    String date2Str = simpleDateFormat.format(data2);
    System.out.println("排序前的时间是=" + date2Str);
    // System.out.println("排序后=" + Arrays.toString(arr));
  }

  // 编写一个堆排序的方法
  public static void heapSort(int arr[]) {
    int temp = 0;
    // 从最后一个非叶子节点（len/2-1）开始往前构造
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
      adjustHeap(arr, i, arr.length);
    }

    /*
    每一轮将根节点（最大值） 与 最后一个叶子节点（数组最后一个元素） 交换），从小到大排序
    然后调整 整颗树为大顶堆
     */
    for (int j = arr.length - 1; j > 0; j--) {
      temp = arr[j];
      arr[j] = arr[0];
      arr[0] = temp;
      adjustHeap(arr, 0, j);
    }
  }

  /**
   * 对于大顶堆(从小到大排序)而言：每个子树的都是大顶堆 && 左、右孩子 < 根 功能： 完成 将以arr[i]节点为根的子树调整成大顶堆
   *
   * @param arr 待调整的数组
   * @param i 子树根节点的下标
   * @param length 表示对多少个元素继续调整， length 是在逐渐的减少（最大值都堆在后面）
   */
  public static void adjustHeap(int[] arr, int i, int length) {
    int temp = arr[i];
    // 2k+1、2k+2分别是左右孩子下标
    // 实际上每一次循环都是调整一棵子树，所以 ;k = k * 2 + 1其实是在初始化
    for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
      if (k + 1 < length && arr[k] < arr[k + 1]) { // 说明左子结点的值小于右子结点的值
        k++; // k 指向右子结点
      } // 此时 k 是左右孩子中最大者的下标
      // 如果子结点大于父结点,即发生了交换,注意：此时arr[k]没有赋值！！why?
      // 本函数的第一行 temp 是第一次调整的根节点值，假设发生了交换，那么下一次调整的根节点值还是temp
      // 没必要换，有可能会被左右孩子再次覆盖，等到啥时候 temp 在当前调整的子树(根索引 i) 中最大了，循环就退出了
      if (arr[k] > temp) {
        arr[i] = arr[k]; // 把较大的值赋给当前结点,注意此时没有将父节点的值
        // 发生了 i和 k的交换，于是乎需要再以 i 为子树进行调整大顶堆，本来这里可以用递归的，写成了非递归的方式
        i = k; // i 指向 k（新的子树根）,继续循环
      } else {
        break;
      }
    }

    arr[i] = temp; // 将temp值放到调整后的位置
  }
}
